This application is related in general to VLSI CAD design, and in specific to an apparatus and method for traversing a design that uses a lightweight occurrence model.
Prior computer aided design (CAD) systems represent designs in a hierarchical connectivity form that provides design information to system designers with different levels of abstraction. An example of such a schematic configuration 100 is shown in FIG. 1, which depicts the relationships between a cell 101, a port 102, a net 103, an instance 104, and a port instance 105. Such a configuration is known as a folded connectivity model. The cell block 101 describes a device or structure of the system, e.g., a full adder. A cell contains collections of instances of other cells, nets (which are wires) and the external interfaces to the cell (ports). The net block 103 describes the wires that make up the internal connections within the cell block. The port block 102 describes the interface to the cell and provides the connection points for the nets (wires) to carry (xe2x80x9cCoxe2x80x9d) signals into and out of the cell block""s logic.
As stated above, a cell block provides the definition of a device or structure. Once a cell has been defined, it can then be instantiated (wherein an instance block 104 is created of that cell), so that it may be used in other cell definitions. In this way, a design hierarchy can be created. The instance block describes the devices or structures used to form the functionality of a cell, e.g., for a two bit adder: two full adder cell instances are created. Just as an instance records the instantiation (or use of) a cell block, the port instance block 105 records the instantiation of the ports on the cell. The port instances allow us to record the specific nets that are connected to a given instance.
The hierarchical nature of the information stored in the folded connectivity model is shown by way of example only in FIGS. 2A-2C. FIG. 2A depicts the highest level of hierarchy, that is cell block 200, which is a two bit adder. The two bit adder block has 8 ports (the inputs A1, B1, A0, B0, Cin; and the outputs Cout, S1, and S0). It contains the nets that are connected to these ports (A1, B1, A0, B0, Cin, Cout, S1, and S0), in addition to one internal net (Co) which is not connected to a port on the cell boundary, but is none-the-less a net contained within the two bit adder cell definition. Finally, the two bit adder contains two instances, FA0 block 202 and FA1 block 203, each of which are instances of a full adder (or a one-bit adder).
FIG. 2B depicts the next lower level of the hierarchy of the system, showing the cell definition for the full adder. Note that the instances FA0 (block 202) and FA1 (block 203) in the top level are described by a cell at the next lower level of hierarchy. The full adder block 201 has 5 ports (input ports A, B, and Cin; the output ports S and Co). It also contains 11 nets (ported nets A, B, Cin, Co, and S; internal nets Co sig_1, sig_2, sig_3, sig_4, and sig_5), and 8 instances (2 instances of an inverter, I1, and I2; 2 instances of a 2-input NOR gate, NO1, NO2; 2 instances of a 2-input XOR gate, XO1 and XO2; and 2 instances of a 2-input NAND gate, NA1 and NA2). Finally, FIG. 2C depicts one of the cells at the lowest level of hierarchy, the 2-input NAND gate. Note that there are 3 other cells at this same level of hierarchy that are not depicted (namely the inverter, the 2-input NOR gate, and the 2-input XOR gate). Additional levels of hierarchy may exist, e.g., one or more levels higher than FIG. 2A.
A folded connectivity model provides a memory efficient representation of source VLSI design data as seen by the VLSI designer. A fundamental limitation of the folded connectivity model, however, is its ability to represent a truly unique addressable object for each object created across the many levels of design hierarchy. Although this is not an issue for many existing CAD tools, it is becoming more of an issue for the next generation analysis and design tools which need to analyze design entities that span the hierarchy. The design of FIGS. 2A-2C can be walked through to illustrate the fundamental limitation of a folded connectivity model. In these FIGURES, the top level cell FIG. 2A contains two instances of the cell xe2x80x9cfull_adderxe2x80x9d, FA0 and FA1. The cell xe2x80x9cfull_adderxe2x80x9d contains two instances of the block xe2x80x9cnand_2xe2x80x9d, NA1 and NA2. This information is recorded in the folded connectivity model as shown in FIG. 4. Notice that, in this diagram, there is only one cell 406 for the NA1 and NA2 instances (blocks 415 and 405 respectively). But, when the same design in the form shown in FIG. 3 is viewed, there are in reality, two different occurrences of the instance NA1 (FA0/NA1 and FA1/NA1). The same is true for the instance NA2 (and, as a result, the nets contained within the describing cells for each of these instances). The folded connectivity model only records that a single instance of cell xe2x80x9cnand_2xe2x80x9d named NA1 is an element of the cell xe2x80x9cfull_adderxe2x80x9d.
A common technique used to avoid this problem is to perform a xe2x80x98flatteningxe2x80x99 process. The process of flattening a hierarchical design removes all intermediate levels of hierarchy, so only primitive elements exist. There are two primary problems with flattening. First, flattening uses a great deal of computer memory. With today""s microprocessor designs, it is often impossible to flatten the entire hierarchy. The second problem is that flattening is a one-way process. Once flattened, it is impractical to relate flattened circuit elements back to a hierarchical view.
For these reasons, the occurrence (or unfolded) model representation is becoming a more important representation for many of today""s CAD tools. In a typical occurrence model, each and every cell is stored, including those cells that are duplicated, while retaining the notion of the original design hierarchy. The primary advantage of an occurrence model is that it allows tools to obtain the benefits of flattening (being able to see a flattened view of the design and the interconnecting nets that span hierarchy) without losing hierarchical information. In addition, using an occurrence model gives some flexibility to the tool developer, so that they do not have to build a model to represent the entire design, only for those pieces currently being evaluated. As an example, each adder 202 and 203 is stored separately in the model, as well as each second NAND (N2) circuit 205, 208 or each adder, and each N2 transistor 207, 209 of N2 circuit, as shown in FIG. 3. FIG. 3 depicts the multi-level view of the cell of FIG. 1 with the different levels of the example of FIGS. 2A-2C. (Note that for simplicity, the other elements of the circuit, as well as the sub-elements, e.g., I1, I2, XO1, XO2, NO1, and NO2 are not shown.) However, modern IC circuits, e.g., processors, comprise millions of instances. Thus, the size of the model quickly becomes large as the lower levels are added to the model. Current computer systems do not have adequate memory to store the complete occurrence model. However, the lower levels are becoming more important to designers. The presence of the lower levels in the model allows for more detailed analysis of the system, e.g., for parasitic losses from the net connections, which thereby improves the speed and efficiency of the system.
FIG. 4 depicts a partial example of the in-memory representation of the folded connectivity model for the schematic design described in FIG. 2. In this model, only one copy of lower level instances are maintained. Pointers 409-414 are used to associate an upper level cell with lower level instances of that cell. FIG. 4 models the same example as shown in FIGS. 2A-2C and 3. This model does not store specific instance and net occurrence information. Instead, each instance of a cell points to a generic higher level cell known as the describer cell). For example, the 2 bit adder cell 400 includes two instances of fall adders 402, 403. Each of these instances 402, 403 point, via pointers 410, 409 to the same full adder describer cell 404. Full adders other than instances 402, 403 will also point to full adder cell 404. Thus, less information is stored for the model. This describer relationship between instances and cells using a describing cell pointer is carried down through the different levels of the design hierarchy, e.g. NAND circuits 405, 415 both point to NAND cell 406, and transistors 407, 416 both point to P cell 408. Thus the folded model will only have one cell for each instance type, whereas the occurrence model will have a different cell for each occurrence of each instance. For example, the folded model has only one cell for the P transistor, namely cell 408, while the occurrence model, as shown in FIG. 3 has four cells (or unique occurrences of the cell), one for each of P1 and P2 of FA0, and P1 and P2 of FA1 (note that additional P cells are likely to be present in the occurrence model, since XO1, XO2, NO1, NO2, I1, and I2 are also likely to use P transistor as sub-elements, but are not shown in FIG. 3). Thus, the folded model is significantly smaller than the occurrence model. Note that the folded model would include port information, which has not been shown in FIG. 4 for simplicity. Also FIG. 4 does not depict all of the cells, e.g., NO1 or NO2, for simplicity.
However, the folded model does not store any occurrence specific information. This means that analysis performed on the model will not accurately reflect some of the phyisical aspects of the actual design. For example, the analysis for delay or parasitic effects will not be accurate, since the context of each instance is not stored in the design. As only a generic cell is stored for each instance type, then the same information will be used in the analysis of each instance in design. In actuality, each instance is different. For example, only one set of information for the Y net will be stored in the folded model, however, each occurrence of the Y net is different, e.g., each occurrence has different delays and/or parasitic effects because, for example, of the different placement for each Y net. However, the folded model does not store these differences, and thus will not provide accurate analysis of the design.
Furthermore, analysis of the folded model is difficult because traversing the net signals up and down through the hierarchy is hindered because of the lack of information. Using the 2_BIT_ADD as an example: there is a net b in the middle level of the hierarchy of the system (full adder FIG. 2B). Net B connects to three instance NO1, XO1, and NA1. Suppose a designer wants to trace down timing delay information and therefore needs to go down to the next lower level, for example, to the net Y in NA1 that connects to net B. However, in the folded model, it is very difficult to find which nets on the lower (or higher levels) connect to the current net, since different nets belong to different cells and there is no information in the folded model that describes the lower level connections of the current net B at the lower level cell instance NO1, XO1, and NA1. (The higher level net connections at higher level 2_BIT_ADD) Using port and port instance, the corresponding net can be found at the next level, such as Y in NA. However, designers still cannot tell the differences between net Y 211 and net Y 212, since there is only one Y 420 under Cell Block NA 406, and both net Y 211 and net Y 212 belong to instance NA1415. This difficulty will also apply to net traverse to the upper level in the hierarchy as well. Therefore, efficiently tracing net signals up and down in the hierarchy is a big challenge for the prior art design tools.
Designers may use hash tables to store the some unique instance information that is not stored in the folded model, such as the timing delay data for net Y 211 and net Y 212. Note that such tables are not part of the folded model and are stored separately from the model. Tables are created by the designers and include information that designer is interested in using in the analysis of the design. However, models that use these tables are not memory efficient and tend to run slow because poor homemade designs. Also the tables are transient, they are maintained only for the analysis of interest and then discarded. This is because each device needs its own hash table. Thus, the homemade hash tables are not portable, i.e., the hash tables cannot be reused by the different designers working on the larger system. Each designer creates their own tables. Hash tables allow designers to write certain net information into files. When following port and port instances to get to the desired level instance, the corresponding file is opened to retrieve the necessary information. However, this is not memory efficient and is slow and not reusable by different applications.
The prior art fails to provide designers with a mechanism to traverse nets up and down in the hierarchy, which is critical for any global net based analysis application such as timing analysis.
The present invention is directed to a system and method that traverses net occurrences of a light weight occurrence model.
The lightweight occurrence model preferably uses the arrangement of the folded model, but includes occurrence nodes that are associated with the folded model. As a result, the lightweight occurrence model augments the arrangement of the folded model in order to include the occurrence nodes (the missing context) and then provides a rich API to allow programmers to traverse through the occurrence nodes. There is preferably at least one occurrence node for each cell instance or net in the folded model. Each occurrence node includes occurrence specific data or a pointer to such data, a pointer to an owner occurrence node, and a pointer to a folded model instance. Thus, most of the information that is present in a full occurrence model can be included in the inventive lightweight occurrence model.
In order to keep the occurrence model lightweight, information that can be obtained from the folded model (such as the relationships between ports, port instances, and nets) are preferably not duplicated in the in-memory representation. This invention allows a user to move up or down the net hierarchy (one level at a time) without needing to know the details of the implementation or the details of the relationships to the folded connectivity model. Occurrences of ports are not maintained because this information can be obtained from the folded model and the inclusion of them in the occurrence model would increase the memory use by approximately two orders of magnitude. Therefore, the ability to easily move up and down the net hierarchy without having to know the implementation details is essential in making a usable occurrence model. This is accomplished by providing two iterators for occurrence nets that provide the illusion that the model stores all of the occurrence nets connected to any given occurrence net one level above or below in hierarchy, yielding a very simple and abstract interface for the user despite the fact that very complex computation is occurring within the iterators.
The invention begins the traversal by initializing the inventive iterator with information about the current occurrence net from the inventive occurrence node that describes the occurrence net""s owner and folded model describer. In traversing down, a port iterator is preferably used, while in traversing up a port instance iterator is preferably used. This is because of the design convention that from the outside of an object a connection is a port instance, while from the inside, the connection is a port.
In traversing up, the iterator finds the next port that connects to the folded model net indicated by the describer used during initialization. The iterator then locates the instance in the folded model pointed to by the describer of the owner of the net object. Next, using the instance and the next port, the iterator locates the corresponding port instance. Since each port instance can only connect to one net, then the iterator can retrieve the net that connects to the port instance, which is the folded model net that is one level higher in hierarchy then the original occurrence net object. The iterator then uses the net object owner""s owner pointer as a search key in searching a map container of the retrieved folded model net. This search should find the occurrence net object that is associated with the folded model net, and is one level higher in hierarchy than the original occurrence net object. If there is no match in the search, the iterator repeats the operation for the next port that is connected to the folded model. If during operation, the iterator encounters nulls, then the iterator ends the operation.
In traversing down, the iterator finds the next port instance that connects to the folded model net indicated by the describer used during initialization. The iterator then retrieves the port that describes the port instance. Since each port can connect to only one net, the iterator then retrieves the net that is connected to the port in the folded model. The iterator uses the owner of the net object as a search key to search a map container of the port instance""s owner, which is an instance. This search yields the occurrence cell that owns the net object that is one level lower in hierarchy than that of the original net object. This occurrence cell is used as a search key to search a container of the retrieved net. This search should find the occurrence net object that is associated with the folded model net, and is one level lower in hierarchy than the original occurrence net object. If there is no match in this search, the iterator repeats the operation for the next port instance that is connected to the folded model. This search may be repeated to find additional occurrence net objects that are one level lower than the original net object. If during operation, the iterator encounters nulls, then the iterator ends the operation.
The present invention is directed to a system and method which facilitates traversal of a lightweight folded occurrence model which includes aspects of both the folded model and the occurrence model.
The inventive lightweight occurrence model uses the arrangement of the folded model but includes occurrence nodes that are associated with the folded model. There is at least one occurrence node for each instance of an object type in the model. Each occurrence node includes occurrence specific data or a pointer to such data, a pointer to a parent occurrence node, and a pointer to a folded model instance. Thus, most of the information that is present in a full occurrence model can be included in the inventive lightweight occurrence model. Since the inventive occurrence model is smaller than the full occurrence model, the entirety of complex circuit designs, e.g., microprocessors, can be represented by the inventive lightweight occurrence model. Thus, low level characteristics of the design, e.g., parasitics, can be examined.
The pointers, or other abstract interfaces, allows the information of the nodes of the folded model to be altered to include the unique data of the instances of the occurrence model, including its hierarchical location in the model. Thus, the entirety of the full occurrence model can be represented by the inventive lightweight occurrence model, depending upon the amount of specific data associated with the node (either stored in the node or pointed to by the node). Note that the occurrence node names do not have to be stored in the nodes. The name of the node, if needed for analysis and not stored, can be constructed from information in the inventive light weight occurrence model. Note that the occurrence nodes do not store information that is already present in the folded model, e.g., information on child nodes and/or information about the relationships of ports, cells, and nets. Consequently, the memory required for the inventive lightweight occurrence model is significantly less than that required for the full occurrence model. For example, an inventive node storing only three pointer may require 12 bytes, while a full occurrence node may require 40 or more bytes, meaning that the inventive lightweight occurrence model would only require about 30% of the memory required for the full occurrence model.
Another aspect of the present invention is that the lightweight occurrence model may be displayed to a user, such that only a desired level of hierarchy for a desired portion of the model is shown to the user. In the prior art, the full occurrence model forces the folded model to be unfolded to the lowest level of the model. Note that this allows the model to have more detailed (lower level) information to be stored for a particular portion, while having only less detailed (higher level) information stored for the remainder of the model. This allows a partial tree to be used, with some branches having more detailed information than other branches.
As stated above, the occurrence node names do not have to be stored in the nodes. However, the model needs to work with tools that require node names for performing analysis on the designs that use the model. Typically, the analysis is hierarchical based analysis, and thus hierarchical names are required. However, in the invention, the names of the nodes can be constructed from information in the inventive light weight occurrence model, e.g., the parent node pointers, the folded instance pointers, etc. This is one of the ways that the inventive lightweight occurrence model appears to the user to be a full occurrence model.
The inventive lightweight occurrence model maintains the instance specific information in a more permanent and organized manner than that of the prior art. The hash tables used by the prior art are external from the model. The hash tables are also written by a designer for their own use and are discarded when that use is finished. Information needed at a subsequent time and/or by a different designer is rewritten into a new hash table. Consequently, the use of hash tables results in error prone and inconsistent analysis. Thus, the specific information for the inventive model needs only to be written once and is maintained with the inventive model.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims. The novel features which are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present invention.